package jjn.round1;

/**
 * @author Jjn
 * @since 2022/10/6 17:12
 */
public class LeetCode977_ThreeEqualParts {
    public int[] threeEqualParts(int[] arr) {
        int[] failedResult = new int[]{-1, -1};
        int sum = 0;
        int[] countArray = new int[arr.length + 1];
        int oneCount = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (arr[i] == 1) {
                countArray[++oneCount] = i;
            }
        }
        if (sum == 0) {
            return new int[]{0, 2};
        }
        if (sum % 3 != 0) {
            return failedResult;
        }
        int range = sum / 3;
        int firstAppearance = countArray[1];
        int secondAppearance = countArray[range + 1];
        int thirdAppearance = countArray[range * 2 + 1];
        int first = firstAppearance, second = secondAppearance, third = thirdAppearance;
        for (; third < arr.length && first < secondAppearance && second < thirdAppearance; first++, second++, third++) {
            if (arr[first] != arr[second] || arr[first] != arr[third]) {
                break;
            }
        }
        if (third < arr.length) {
            return failedResult;
        }
        return new int[]{first - 1, second};
    }

}
